package SortAlgorithm;

import org.junit.Test;

/**
 * @Author ：xu_xiaofeng.
 * @Date ：Created in 11:17 2021/3/9
 * @Description： 后续练手用的。。。
 */
public class newMergeSort {
    // 归并排序包括两个部分，一部分是划分，还有一部分是排序

    // 归并排序入口
    void mergeSort(int[] arr) {

        // 分配一个临时数组用于排序
        int[] tempArr = new int[arr.length];

        mSort(arr, tempArr, 0, arr.length - 1);

    }

    // 分治的主体
    void mSort(int[] arr, int[] tempArr, int start, int end) {
        // 跳出递归的条件，序列中只剩一个元素，显然是有序的
        if (start < end) {
            int mid = (start + end) >> 1;//找中间索引的位置
            // 递归划分左半部分
            mSort(arr, tempArr, start, mid);

            // 递归划分右半部分
            mSort(arr, tempArr, mid + 1, end);

            // 合并已经排序的左右部分
            merge(arr, tempArr, start, mid, end);
        }
    }

    // 合并两个已经排序的左右序列
    void merge(int[] arr, int[] tempArr, int start, int mid, int end) {
        // 标记左半区域第一个未排序的位置
        int l_pos = start;
        // 标记右半区域第一个未排序的位置
        int r_pos = mid + 1;
        // 标记临时数组的位置
        int pos = start;
        // 合并
        while (l_pos <= mid && r_pos <= end) {
            if (arr[l_pos] <= arr[r_pos]) {
                tempArr[pos++] = arr[l_pos++];
            } else {
                tempArr[pos++] = arr[r_pos++];
            }
        }

        // 合并左半区域剩余元素
        while (l_pos <= mid) {
            tempArr[pos++] = arr[l_pos++];
        }
        // 合并右半区域剩余元素
        while (r_pos <= end) {
            tempArr[pos++] = arr[r_pos++];
        }
        // 将临时数组copy至原数组
        while (start <= end) {
            arr[start] = tempArr[start];
            start++;
        }
    }

    @Test
    public void test(){
        int[] testArray = {5, 8, 4, 6, 7, 2, 1, 10};

        mergeSort(testArray);

        for(int i :testArray){
            System.out.print(i+",");
        }
    }
}
